# 递归就是来解决重复问题
"""
解决递归难题的神奇四步
1: 定义一个size-n问题：你需要解决阶乘的问题-->n!-->def factorial(n)
2: 找到上述问题的终止条件以及在该条件下的返回值-->当n==0的时候，返回值是1
3: 定义size-m问题（n-->m），m=n-1;在很多情况下确实是n-1问题，但是也有例外：归并排序：m=1/2n
4: 通过第三步的分析，构建出了size-n问题的解
"""


# 阶乘：n! == n*(n-1)*(n-2)*.....1
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)


"""
汉诺塔（hanoi tower）游戏
在汉诺塔游戏中，有三个柱子和若干个大小不一的盘子。
初始时，所有盘子都在第一根柱子上，目标是将所有盘子移动到第三根柱子上，且在移动过程中遵循以下规则：
每次只能移动一个盘子。
任何时候，较大的盘子不能放在较小盘子上。
"""


# 1: 定义一个size-n问题：方法叫hanoi
def hanoi(n, source, center, destination):
    # 2: 判断终止条件，并且终止条件的返回值--> 当n=1时，之间将圆盘从Source移动到Destination
    if n == 1:
        print("将第1块盘从{}移动到{}".format(source, destination))
        return
    # 3: 判断size-m问题，n-->m，m = n - 1
    # 4: 通过第三步的分析，构建出了size-n问题的解
    # 4.1：Source --> Center
    # 4.2: Center --> Destination
    hanoi(n - 1, source, destination, center)
    print("将第{}块盘从{}移动到{}".format(n, source, destination))
    hanoi(n - 1, center, source, destination)


# 斐波那契函数
"""
fib(N)={
  0 (N == 0)
  1 (N == 1)
  fib(N-1)+fib(N-2) (N >= 2)
}
"""

def fib1(n):
    if n == 1: return 1
    if n == 2: return 1
    return fib1(n-1) + fib1(n-2)

def fib2(n):
    a = list()
    a.append(1)
    a.append(1)
    for i in range(2,n):
        a.append(a[i-1]+a[i-2])
    return a[n-1]


def fib3(n):
    a = 1
    b = 1
    for i in range(3,n+1):
        c = a + b
        a = b
        b = c
    return c

#print(fib1(5))
#print(fib2(5))
#print(fib3(5))
